/**
 * 18. 四数之和
 * 中等
 * 相关标签
 * conpanies icon
 * 相关企业
 * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
 *
 * 0 <= a, b, c, d < n
 * a、b、c 和 d 互不相同
 * nums[a] + nums[b] + nums[c] + nums[d] == target
 * 你可以按 任意顺序 返回答案 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,0,-1,0,-2,2], target = 0
 * 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
 * 示例 2：
 *
 * 输入：nums = [2,2,2,2,2], target = 8
 * 输出：[[2,2,2,2]]
 */

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  nums.sort((a, b) => a - b)

  const res = []
  kSum(nums, target, 4, 0, [], res)

  return res
}

function kSum(nums, target, k, i, acc, results) {
  if (nums[i] * k > target || nums[nums.length - 1] * k < target) {
    return
  }

  if (k > 2) {
    for (let j = i; j <= nums.length - k; j++) {
      if (j === i || nums[j] > nums[j - 1]) {
        kSum(nums, target - nums[j], k - 1, j + 1, [...acc, nums[j]], results)
      }
    }
  } else {
    twoSum(nums, target, i, acc, results)
  }
}

function twoSum(nums, target, i, acc, results) {
  let lo = i
  let hi = nums.length - 1
  while (lo < hi) {
    const sum = nums[lo] + nums[hi]
    if (sum === target) {
      results.push([...acc, nums[lo], nums[hi]])
      while (nums[lo] === nums[lo + 1]) lo++
      while (nums[hi] === nums[hi - 1]) hi--
      lo++
      hi--
    } else if (sum < target) {
      lo++
    } else {
      hi--
    }
  }
}

// 输入：nums = [1,0,-1,0,-2,2], target = 0
// 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
console.log(fourSum([1, 0, -1, 0, -2, 2], 0))

// 输入：nums = [2,2,2,2,2], target = 8
// 输出：[[2,2,2,2]]
console.log(fourSum([2, 2, 2, 2, 2], 8))
